\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage{amsmath}
\usepackage{ctex}
\usepackage{listings}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{graphicx}
\usepackage{tikz}

\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-0.5cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\begin{document}
% =================================================
\title{Design Idea}

\author{徐翊钧 3220101901
  \thanks{Electronic address: \texttt{3220101901@zju.deu.cn}}}
\affil{(Qiangji2201), Zhejiang University }

\maketitle

\ctexset{
    abstractname = {Abstract}
}

\begin{abstract}  
This document outlines the design of a numerical analysis project, encompassing the design of both piecewise polynomial (pp) splines and B-splines, as well as the conceptualization of spline curve fitting functions. The project aims to achieve linear and cubic pp-splines with three types of boundary conditions; B-splines of arbitrary order with specified boundary conditions; and spline curve fitting in two-dimensional planes, three-dimensional space, and on the surface of a sphere. The implementation is verified through a series of assignment problems.
\end{abstract}

% ============================================
\part{PP Spline design idea.}

% ============================================
\section{SplineBase}
The \texttt{SplineBase} class is a base class designed for spline interpolation. It provides a foundation for various types of spline interpolations, allowing for easy extension and customization.

\subsection{Member Variables}
The \texttt{SplineBase} class contains the following member variables:

\begin{itemize}
    \item \texttt{xData}, \texttt{yData}: These are vectors of type \texttt{std::vector<double>} that store the x and y coordinates of the data points, respectively.
\end{itemize}

\subsection{Interfaces}
The \texttt{SplineBase} class provides the following interfaces:

\begin{itemize}
    \item \texttt{SplineBase()}: Default constructor.
    \item \texttt{SplineBase(const SplineBase \&)}: Copy constructor.
    \item \texttt{SplineBase(SplineBase \&\&)}: Move constructor.
    \item \texttt{SplineBase(std::vector<double> x, std::vector<double> y)}: Constructor that initializes the \texttt{xData} and \texttt{yData} vectors.
    \item \texttt{SplineBase \&operator=(const SplineBase \&)}: Copy assignment operator.
    \item \texttt{SplineBase \&operator=(SplineBase \&\&)}: Move assignment operator.
    \item \texttt{virtual double interpolate(double x) const = 0}: Pure virtual function for interpolation. This function must be implemented by any derived class.
    \item \texttt{size\_t get\_closest\_left\_idx(double x) const}: Returns the index of the closest data point that is less than or equal to the given x value.
    \item \texttt{void draw(std::string file\_name) const}: Draws the spline curve and saves it to a file.
\end{itemize}

\subsubsection{Member Variable Details}
\begin{description}
    \item[xData] This vector stores the x-coordinates of the data points. It is initialized to an empty vector.
    \item[yData] This vector stores the y-coordinates of the data points. It is initialized to an empty vector.
\end{description}

\subsubsection{Interface Details}
\begin{description}
    \item[get\_closest\_left\_idx] This function uses the \texttt{std::upper\_bound} algorithm to find the iterator to the first element that is greater than the given x value. It then calculates the index of the closest data point that is less than or equal to the given x value.
    \item[draw] This function generates a smooth curve through the data points using the interpolation function. It then plots the curve and the data points using the \texttt{matplotlibcpp} library and saves the plot to a file specified by \texttt{file\_name}.
\end{description}
% ============================================

\section{LinearSpline}
The \texttt{LinearSpline} class is a derived class of \texttt{SplineBase}, implementing linear interpolation between data points. It inherits the basic structure and functionality from \texttt{SplineBase} and extends it with linear interpolation specifics.

\subsection{Inheritance Hierarchy}
\begin{center}
\begin{tikzpicture}
  \node (base) at (0,0) {SplineBase};
  \node (derived) at (0,-1.5) {LinearSpline};
  \draw[thick,->] (derived) -- (base);
\end{tikzpicture}
\end{center}

\subsection{Member Variables}
The \texttt{LinearSpline} class introduces the following member variable in addition to those inherited from \texttt{SplineBase}:

\begin{itemize}
    \item \texttt{a}: A vector of type \texttt{std::vector<double>} that stores the slope of the linear segments between data points.
\end{itemize}

\subsection{Interfaces}
The \texttt{LinearSpline} class provides the following interfaces:

\begin{itemize}
    \item \texttt{LinearSpline()}: Default constructor.
    \item \texttt{LinearSpline(LinearSpline \&\&)}: Move constructor (deleted).
    \item \texttt{LinearSpline \&operator=(const LinearSpline \&)}: Copy assignment operator (default).
    \item \texttt{LinearSpline \&operator=(LinearSpline \&\&)}: Move assignment operator (deleted).
    \item \texttt{LinearSpline(const LinearSpline \&)}: Copy constructor (default).
    \item \texttt{LinearSpline(std::vector<double> x, std::vector<double> y)}: Constructor that initializes the \texttt{xData} and \texttt{yData} vectors and sets up the splines.
    \item \texttt{void setupSplines()}: Computes the slopes of the linear segments.
    \item \texttt{double interpolate(double x) const}: Computes the interpolated value at a given x.
    \item \texttt{double derivative(double x) const}: Computes the derivative at a given x.
\end{itemize}

\subsubsection{Member Variable Details}
\begin{description}
    \item[a] This vector stores the slope of each linear segment between consecutive data points. It is calculated in the \texttt{setupSplines} method.
\end{description}

\subsubsection{Interface Details}
\begin{description}
    \item[setupSplines] This method calculates the slope of each linear segment between consecutive data points and stores them in the \texttt{a} vector.
    \item[interpolate] This method uses the slope and a data point to compute the interpolated value at a given x.
    \item[derivative] This method returns the slope of the linear segment at a given x, which is the derivative of the linear function at that point.
\end{description}
% ============================================

\section{CubicSpline}
The \texttt{CubicSpline} class is a derived class of \texttt{SplineBase}, implementing cubic spline interpolation. It inherits the basic structure and functionality from \texttt{SplineBase} and extends it with cubic spline interpolation specifics.

\subsection{Inheritance Hierarchy}
\begin{center}
\begin{tikzpicture}
  \node (base) at (0,0) {SplineBase};
  \node (derived) at (0,-1.5) {CubicSpline};
  \draw[thick,->] (derived) -- (base);
\end{tikzpicture}
\end{center}

\subsection{Member Variables}
The \texttt{CubicSpline} class introduces the following member variables in addition to those inherited from \texttt{SplineBase}:

\begin{itemize}
    \item \texttt{bd\_type boundary}: Stores the boundary condition type.
    \item \texttt{vector\_type a, b, c}: Vectors that store the coefficients for the cubic spline equation \(a(x-x_i)^3 + b(x-x_i)^2 + c(x-x_i) + y_i\).
    \item \texttt{double l\_bd = 0, r\_bd = 0}: Stores the left and right boundary values.
\end{itemize}

\subsection{Interfaces}
The \texttt{CubicSpline} class provides the following interfaces, some of which override or extend those from \texttt{SplineBase}:

\begin{itemize}
    \item \texttt{CubicSpline()}: Default constructor.
    \item \texttt{CubicSpline(vector\_type x, vector\_type y, bd\_type type=natural, double l\_val = 0, double r\_val = 0)}: Constructor that initializes the spline with data points and boundary conditions.
    \item \texttt{void setData(vector\_type x, vector\_type y)}: Sets the data points for the spline.
    \item \texttt{void setBoundary(bd\_type bd, double l\_val=0, double r\_val=0)}: Sets the boundary conditions for the spline.
    \item \texttt{void setupSplines()}: Computes the coefficients for the cubic spline.
    \item \texttt{double interpolate(double x) const}: Computes the interpolated value at a given x.
    \item \texttt{double derivative(double x) const}: Computes the derivative at a given x.
    \item \texttt{double secondDerivative(double x) const}: Computes the second derivative at a given x.
    \item \texttt{void draw(std::string file\_name) const}: Draws the spline curve and saves it to a file, overriding the base class method.
    \item \texttt{void check()}: Checks the validity of the data for periodic boundary conditions.
\end{itemize}

\subsubsection{Interface Details}
\begin{description}
    \item[setupSplines] This method computes the coefficients \(a\), \(b\), and \(c\) for the cubic spline equation based on the boundary conditions.
    \item[interpolate] This method uses the computed coefficients to find the interpolated value at a given x.
    \item[derivative] This method calculates the first derivative of the cubic spline at a given x.
    \item[secondDerivative] This method calculates the second derivative of the cubic spline at a given x.
    \item[draw] This method overrides the base class method to provide specific drawing functionality for cubic splines.
    \item[check] This method checks if the data is valid for periodic boundary conditions, throwing an exception if not.
\end{description}
% ============================================
\part{B Spline design idea}
\setcounter{section}{0}
\section{Introduction of BSpline}
The \texttt{BSpline} class provides an implementation of B-spline interpolation, which is independent of the piecewise polynomial splines. It supports arbitrary degrees for the B-spline basis functions, allowing for flexible and customizable spline interpolation.

\subsection{Class Overview}
The \texttt{BSpline} class is designed to handle B-spline interpolation with arbitrary degrees. It includes methods for setting up the spline, interpolating values, and visualizing the results.

\subsection{Member Variables}
The \texttt{BSpline} class has the following member variables:

\begin{itemize}
    \item \texttt{int degree}: The degree of the B-spline.
    \item \texttt{bd\_type boundary}: The boundary condition type, which can be complete, natural, or periodic.
    \item \texttt{vector\_type knots}: The knots vector used in the computation of the B-spline basis functions.
    \item \texttt{vector\_type xData, yData}: The x and y data points for interpolation.
    \item \texttt{Eigen::VectorXd control\_points}: The control points of the B-spline.
    \item \texttt{double l\_bd, r\_bd}: The left and right boundary values.
\end{itemize}

\subsection{Constructors}
The \texttt{BSpline} class provides the following constructors:

\begin{itemize}
    \item \texttt{BSpline(int deg=3)}: Default constructor with an optional degree parameter.
    \item \texttt{BSpline(int deg, vector\_type xValue, vector\_type yValue, bd\_type bd=natural, double l\_val=0, double r\_val=0)}: Constructor that initializes the B-spline with data points and boundary conditions.
\end{itemize}

\subsection{Member Functions}
The \texttt{BSpline} class provides the following member functions:

\begin{itemize}
    \item \texttt{void setDegree(int deg)}: Sets the degree of the B-spline.
    \item \texttt{void setKnots(vector\_type x)}: Sets the knots vector for the B-spline.
    \item \texttt{void setData(vector\_type x, vector\_type y)}: Sets the data points for interpolation.
    \item \texttt{void setBoundary(bd\_type bd, double l\_val=0, double r\_val=0)}: Sets the boundary conditions for the B-spline.
    \item \texttt{void generateKnots()}: Generates the knots vector based on the data points and degree.
    \item \texttt{void setupSpline()}: Sets up the B-spline interpolation.
    \item \texttt{double interpolate(double t)}: Interpolates a value at a given point \(t\).
    \item \texttt{void draw(std::string file\_name)}: Draws the B-spline curve and saves it to a file.
    \item \texttt{void cardinalQuadratic(int xStart, int xEnd, vector\_type yValue)}: Sets up a cardinal quadratic B-spline.
    \item \texttt{size\_t get\_closest\_left\_idx(double x) const}: Finds the index of the closest left data point to a given x-value.
    \item \texttt{double basicFun(int i, int n, double t)}: Computes the value of the B-spline basis function.
\end{itemize}

\subsection{Arbitrary Degree Support}
The \texttt{BSpline} class supports B-splines of arbitrary degrees. This is achieved by:

\begin{itemize}
    \item Allowing the user to specify the degree of the B-spline through the \texttt{setDegree} function or the constructor.
    \item Adjusting the computation of the knots vector and the B-spline basis functions to accommodate different degrees.
    \item Ensuring that the setup and interpolation methods can handle B-splines of any specified degree.
\end{itemize}

\subsection{Conclusion}
The \texttt{BSpline} class offers a flexible and customizable approach to B-spline interpolation, with support for arbitrary degrees and various boundary conditions. It provides a robust framework for users to perform spline interpolation tasks with different requirements.
% ===============================================

\section{Introduction of Curve Fit}
The \texttt{SplineCurveFit} class is designed to perform curve fitting using B-splines and provides functionality for both regular and spherical curve fitting. It leverages the \texttt{BSpline} class for B-spline interpolation and extends its capabilities to handle 2D and 3D curve fitting with coordinate transformations for spherical fitting.

\subsection{Class Overview}
The \texttt{SplineCurveFit} class offers a comprehensive approach to curve fitting, utilizing B-splines for smooth and accurate interpolation. It supports both 2D and 3D data, with the ability to switch between cumulative and equal-distance knot generation methods.

\subsection{Member Variables}
The \texttt{SplineCurveFit} class has the following member variables:

\begin{itemize}
    \item \texttt{int dimension}: The dimension of the curve fitting (2 for 2D, 3 for 3D).
    \item \texttt{knots\_type kn\_type}: The type of knot generation method used.
    \item \texttt{curve\_type cv\_type}: The type of curve fitting, either regular or ball (spherical).
    \item \texttt{double theta}: The rotation angle used in spherical coordinate transformations.
    \item \texttt{vector\_type xData, yData, zData}: The data points for curve fitting.
    \item \texttt{vector\_type knots}: The knots vector used in B-spline interpolation.
    \item \texttt{spline\_type xCurve, yCurve, zCurve}: The B-spline curves for each dimension.
    \item \texttt{spline\_type xBall, yBall}: The B-spline curves for spherical fitting in 2D projection.
\end{itemize}

\subsection{Constructors}
The \texttt{SplineCurveFit} class provides the following constructors:

\begin{itemize}
    \item \texttt{SplineCurveFit(int dim=2)}: Default constructor with an optional dimension parameter.
    \item \texttt{SplineCurveFit(vector\_type x, vector\_type y, int dim=2, knots\_type type=cumulative)}: Constructor for 2D curve fitting with data points and knot generation method.
    \item \texttt{SplineCurveFit(vector\_type x, vector\_type y, vector\_type z, int dim=3, knots\_type type=cumulative)}: Constructor for 3D curve fitting with data points and knot generation method.
\end{itemize}

\subsection{Member Functions}
The \texttt{SplineCurveFit} class provides the following member functions:

\begin{itemize}
    \item \texttt{void generate\_knots()}: Generates the knots vector based on the data points and dimension.
    \item \texttt{void setDimension(int dim)}: Sets the dimension of the curve fitting.
    \item \texttt{void setData(vector\_type x, vector\_type y, vector\_type z=vector\_type())}: Sets the data points for curve fitting.
    \item \texttt{void setKnots(vector\_type x)}: Sets the knots vector.
    \item \texttt{void checkData()}: Checks the validity of the data points based on the dimension.
    \item \texttt{void setupCurve()}: Sets up the B-spline curves for the given data points and knots.
    \item \texttt{vector\_type interpolate(double t)}: Interpolates a point on the curve at a given parameter \(t\).
    \item \texttt{std::vector<double> ball\_to\_flat(double x, double y, double z)}: Converts spherical coordinates to a 2D projection.
    \item \texttt{std::vector<double> flat\_to\_ball(double X, double Y)}: Converts a 2D projection back to spherical coordinates.
    \item \texttt{void setupBallCurve()}: Sets up the B-spline curves for spherical fitting by projecting 3D spherical points to 2D and back.
\end{itemize}

\subsubsection{B-Spline Interpolation}
The \texttt{SplineCurveFit} class utilizes B-splines for interpolation, providing a flexible and accurate method for curve fitting. B-splines offer the advantage of local control and smoothness, which is essential for complex curve fitting tasks.

\subsubsection{Spherical Curve Fitting}
For spherical curve fitting, the class performs coordinate transformations between spherical and Cartesian coordinates. And use a rotation to avoid project to infinity. This allows for the fitting of curves on the surface of a sphere, with the ability to project and reproject points as needed.

\subsection{Conclusion}
The \texttt{SplineCurveFit} class offers a powerful tool for curve fitting, leveraging B-splines for accuracy and flexibility. Its support for both regular and spherical curve fitting makes it a versatile solution for a wide range of applications.

\end{document}